package algorithm;

import java.util.Arrays;

public class T00354 {
    public static void main(String[] args) {
        int[][] arr = {{4,5},{4,6},{6,7},{2,3},{1,1}};
        System.out.println(new Solution().maxEnvelopes(arr));
    }

    static class Solution {
        public int maxEnvelopes(int[][] envelopes) {
            Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
            int[] dp = new int[envelopes.length];
            Arrays.fill(dp, 1);
            for (int i = 0; i < envelopes.length; i++) {
                for (int j = 0; j < i; j++) {
                    if (envelopes[i][1] > envelopes[j][1]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }
            int res = -1;
            for (int i = 0; i < dp.length; i++) {
                res = Math.max(dp[i], res);
            }
            return res;
        }
    }
}
